import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-11
 * Time: 23:11
 */
class Solution {
//     dfs 回溯 剪枝
//     重点是怎么 去重
    public int[] arr;
    public int length;
    public List<List<Integer>> lists=new ArrayList<>();
    public List<Integer> list=new ArrayList<>();
    public void dfs(int index,int target){
        if(0==target){
            lists.add(new ArrayList<>(list));
            return ;
        }
        // 这个循环作用是 控制 同一个数的 数目
        // 每进入一个函数, 就增加一个
        // 每退出一个函数, 这个数就减少一个
        // 以此来控制 每个数出现的次数, 从而 保证不会出现 重复的结果
        //
        for(int i=index;i<this.length;i++){
            // 剪枝 比需要的数大了
            // 不再往后递归
            if(this.arr[i]>target){
                break;
            }
            // 保证了 不会出现重复
            // 即 一个数字出现的次数 不会相同
            if(i>index&&this.arr[i]==this.arr[i-1]){
                continue;
            }
            // 不是只 遍历 一层(即数字相同的 一层)
            // 是为了 一个数字的数目控制好之后, 让他 往下递归, 寻找结果
            // if(i!=index){
            //     return ;
            // }
            list.add(this.arr[i]);
            // 貌似是 用减法, 效率更高
            dfs(i+1, target-this.arr[i]);
            list.remove(list.size()-1);
            // dfs(i+1, sum, target);
            // 这里不用再 递归 不考虑当前元素 的情况, 原因是, 这里是循环
            // 后面会继续进行递归
            // 如果当前元素是最后一个元素的话
            // 也就没必要递归了, 因为如果不考虑当前元素却满足条件的话, 就已经加入进去了
            // 相当于, 每次都是先进行 不考虑当前元素 的操作
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.arr=candidates;
        this.length=arr.length;
        dfs(0,  target);
        return lists;
    }
}
